package swordoffer.offer32_3;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class DequeSolution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            // 打印奇数层
            List<Integer> list = new ArrayList<>();
            for (int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeFirst();
                list.add(node.val);
                // 把偶数层元素 从左往右 加入队尾
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
            res.add(list);
            if (deque.isEmpty()) {
                break;
            }
            list = new ArrayList<>();
            // 打印偶数层
            for (int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeLast();
                list.add(node.val);
                // 把奇数层元素 从右往左 加入队头
                if (node.right != null) {
                    deque.addFirst(node.right);
                }
                if (node.left != null) {
                    deque.addFirst(node.left);
                }
            }
            res.add(list);
        }
        return res;
    }
}
